큐 (자료구조)

삽입 연산은 큐의 가장 뒷부분, 즉 리어(rear)에 새로운 데이터 요소를 추가하는 작업이다. 이 연산을 인큐(enqueue)라고 부른다. 인큐 연산이 수행되면 리어의 위치는 새롭게 추가된 요소를 가리키도록 한 칸 이동한다.

큐가 비어있는 상태에서 첫 번째 요소를 인큐하면, 프런트(front)와 리어는 모두 그 요소를 가리키게 된다. 이후 요소들이 계속 추가될 때마다 리어 포인터만이 뒤로 이동하며, 프런트 포인터는 가장 먼저 들어온 요소를 고정적으로 가리킨다. 이는 선입선출 원칙의 핵심 동작 방식이다.

배열로 구현된 선형 큐에서 인큐를 수행할 때는 리어 인덱스를 증가시킨 후 해당 위치에 데이터를 저장한다. 반면, 연결 리스트를 이용한 구현에서는 새로운 노드(node)를 생성하여 현재 리어 노드의 다음 노드로 연결하고, 리어 포인터를 이 새 노드로 갱신하는 방식으로 이루어진다.

삭제 연산은 큐의 맨 앞에 위치한 원소를 제거하고 반환하는 작업이다. 이 연산은 큐가 선입선출 방식으로 동작하는 핵심 원리를 구현한다. 큐에서 가장 먼저 들어온 데이터가 가장 먼저 나가게 되므로, 삭제는 항상 프런트라고 불리는 큐의 시작 지점에서만 발생한다. 이 연산은 영어로 디큐(dequeue)라고도 불리며, 큐의 기본 연산 중 가장 중요한 연산에 속한다.

삭제 연산을 수행하기 전에는 반드시 큐가 비어있지 않은지 확인해야 한다. 빈 큐에서 삭제를 시도하는 경우 언더플로우가 발생하여 오류가 나거나 예기치 않은 동작을 일으킬 수 있다. 따라서 대부분의 구현에서는 삭제 전에 isEmpty 연산을 통해 큐의 상태를 먼저 점검하는 것이 일반적이다. 삭제가 성공적으로 이루어지면, 프런트에 있던 원소가 제거되고, 그 다음에 대기 중인 원소가 새로운 프런트가 된다.

이 연산의 동작은 큐의 구현 방식에 따라 세부적으로 달라진다. 배열을 사용한 선형 큐에서는 프런트 인덱스를 하나 증가시키는 방식으로 삭제를 구현한다. 연결 리스트를 이용한 구현에서는 프런트 노드를 제거하고, 그 다음 노드를 새로운 헤드로 설정한다. 원형 큐의 경우에도 인덱스를 증가시키지만, 배열의 끝에 도달하면 다시 처음으로 돌아가는 모듈로 연산이 추가된다.

삭제 연산은 작업 스케줄링, 프린터 대기열 관리, 너비 우선 탐색 알고리즘 등 큐가 활용되는 모든 분야에서 필수적으로 사용된다. 예를 들어, 운영체제의 CPU 스케줄링에서 준비 완료 큐의 맨 앞 작업을 디스패치하거나, 네트워크의 패킷 버퍼에서 도착한 순서대로 데이터를 처리할 때 이 연산이 수행된다.

탐색 연산은 큐의 맨 앞에 위치한 원소를 확인하지만, 그 원소를 제거하지는 않는다. 이 연산은 주로 peek 또는 front라고 불린다. 큐가 비어 있는 상태에서 이 연산을 수행하는 것은 오류를 유발할 수 있으므로, 일반적으로 연산 전에 큐가 비어 있는지 확인하는 isEmpty 연산과 함께 사용된다.

이 연산은 큐의 현재 상태를 확인하는 데 필수적이다. 예를 들어, 작업 스케줄링 시스템에서 다음에 실행될 작업이 무엇인지 확인하거나, 프린터 대기열에서 현재 출력 중인 문서를 확인하는 경우에 활용된다. 또한 너비 우선 탐색 알고리즘에서 다음에 방문할 노드를 결정할 때도 사용된다.

큐의 기본 연산들 중 enqueue와 dequeue가 큐의 내용을 변경하는 반면, peek/front 연산은 단순히 데이터를 읽기만 한다는 점에서 차이가 있다. 이는 큐의 무결성을 유지하면서도 필요한 정보에 접근할 수 있게 해주는 중요한 특징이다.

배열을 이용한 큐 구현은 가장 직관적이고 간단한 방법 중 하나이다. 고정된 크기의 배열과 두 개의 인덱스(포인터)를 사용하여 큐의 앞과 뒤를 추적한다. 일반적으로 front 인덱스는 첫 번째 원소(다음에 제거될 원소)의 위치를, rear 인덱스는 마지막으로 추가된 원소의 위치 또는 새로운 원소가 삽입될 위치를 가리킨다.

초기 상태에서는 큐가 비어 있으므로 front와 rear 인덱스는 보통 -1이나 0으로 초기화한다. enqueue 연산이 수행되면 rear 인덱스를 증가시킨 후 해당 위치에 데이터를 저장한다. dequeue 연산은 front 인덱스가 가리키는 위치의 데이터를 반환하거나 제거한 후 front 인덱스를 증가시킨다. 이 과정에서 front와 rear 인덱스는 배열의 끝을 향해 단방향으로만 이동하게 된다.

이러한 단순한 구현 방식은 한계를 가진다. dequeue 연산이 반복되면 front 인덱스가 계속 증가하여 배열의 앞부분이 비게 되지만, rear 인덱스가 배열의 마지막에 도달하면 더 이상 새로운 원소를 삽입할 수 없는 '포화 상태'로 판단된다. 실제로는 배열 앞쪽에 사용 가능한 공간이 남아 있음에도 불구하고 공간을 활용하지 못하는 문제가 발생하는데, 이를 '잠재적 오버플로우' 또는 '선형 큐'의 단점이라고 한다.

이 문제를 해결하기 위해 고안된 것이 원형 큐이다. 원형 큐는 배열의 끝과 시작이 연결되어 있다고 가정하여, 인덱스가 배열의 마지막 위치에 도달하면 다시 배열의 처음으로 순환하도록 구현한다. 이를 통해 배열 공간을 효율적으로 재사용할 수 있다. 배열 기반 구현의 장점은 연결 리스트를 이용한 구현에 비해 메모리 오버헤드가 적고, 원소에 대한 임의 접근이 가능하며, 일반적으로 캐시 지역성이 더 좋아 성능상 유리할 수 있다는 점이다.

연결 리스트를 이용한 큐 구현은 배열 기반 구현의 단점인 크기 제한 문제를 해결한다. 동적 메모리 할당을 통해 필요에 따라 노드를 추가하거나 제거할 수 있어, 데이터의 개수가 변동성이 큰 상황에 적합하다. 이 방식은 큐의 최대 크기를 사전에 정의할 필요가 없으며, 메모리 공간을 효율적으로 사용할 수 있다는 장점이 있다.

구현은 일반적으로 단일 연결 리스트를 사용하며, 큐의 앞과 뒤를 가리키는 두 개의 포인터를 관리한다. 하나는 프런트라고 하여 삭제 연산이 발생하는 위치를, 다른 하나는 리어라고 하여 삽입 연산이 발생하는 위치를 가리킨다. 연결 리스트의 각 노드는 저장할 데이터와 다음 노드를 가리키는 링크로 구성된다.

이 구현 방식에서는 큐가 비어 있을 때 프런트와 리어 포인터가 모두 NULL을 가리키도록 초기화한다. 첫 번째 요소가 삽입될 때는 이 두 포인터가 모두 새 노드를 가리키게 되며, 이후 삽입 연산에서는 리어 포인터만 이동한다. 모든 요소가 제거되어 큐가 다시 빈 상태가 되면, 두 포인터는 다시 NULL로 설정된다. 이 방법은 자료구조의 기본 개념을 이해하고 동적 메모리 할당을 익히는 데 좋은 예시가 된다.

선형 큐는 가장 기본적인 큐의 형태로, 데이터를 저장할 수 있는 연속된 메모리 공간(주로 배열)을 사용하며, 데이터의 삽입과 삭제가 각각 한쪽 끝에서만 일어나는 구조이다. 삽입이 일어나는 끝을 후단, 삭제가 일어나는 끝을 전단이라고 부른다. 데이터는 후단에서만 삽입되고, 전단에서만 삭제되므로, 가장 먼저 들어온 데이터가 가장 먼저 나가는 선입선출 방식을 그대로 구현한다.

이 구조는 직관적이고 구현이 간단하지만, 한 가지 주요한 문제점을 가지고 있다. 데이터를 삽입하고 삭제하는 과정에서 전단과 후단의 인덱스가 계속 증가하기만 하면, 배열의 앞부분에 빈 공간이 생기더라도 후단 인덱스가 배열의 끝에 도달하면 더 이상 데이터를 삽입할 수 없는 포화 상태로 잘못 판단하게 된다. 이를 잔여 공간 문제 또는 가짜 오버플로우라고 한다.

이 문제를 해결하기 위한 방법으로는 원형 큐가 개발되었다. 원형 큐는 선형 배열을 원형으로 간주하여, 인덱스가 배열의 끝에 도달하면 다시 배열의 처음으로 돌아오도록 구현함으로써 빈 공간을 효율적으로 재사용한다. 반면, 선형 큐는 이러한 재사용이 불가능하여 메모리 효율성이 떨어진다는 단점이 있다.

따라서 선형 큐는 학습 목적이나 매우 제한된 환경을 제외하고는 실제 시스템 프로그래밍이나 응용 소프트웨어에서는 잘 사용되지 않으며, 보다 효율적인 원형 큐나 연결 리스트 기반의 큐 구현이 선호된다.

원형 큐는 선형 큐의 한계를 보완하기 위해 고안된 자료구조이다. 선형 큐는 배열로 구현할 경우, 데이터를 삭제(dequeue)하면 앞쪽에 빈 공간이 생기지만, 새로운 데이터는 항상 뒤쪽에만 삽입(enqueue)되기 때문에 점점 사용 가능한 공간이 줄어드는 문제가 있다. 이는 배열의 앞부분 공간을 재사용하지 못하게 하는 낭비를 초래한다. 원형 큐는 이러한 문제를 해결하기 위해 배열의 마지막 인덱스와 첫 번째 인덱스를 논리적으로 연결하여 원형 구조를 만든다.

원형 큐의 핵심은 배열을 원형 버퍼처럼 사용하는 것이다. 이를 위해 두 개의 포인터, 즉 데이터를 삽입할 위치를 가리키는 rear 포인터와 데이터를 삭제할 위치를 가리키는 front 포인터를 사용한다. 데이터를 삽입할 때는 rear가 가리키는 위치에 저장한 후, rear를 다음 위치로 이동시킨다. 데이터를 삭제할 때는 front가 가리키는 위치의 값을 반환한 후, front를 다음 위치로 이동시킨다. 포인터가 배열의 끝에 도달하면, 다음 위치는 배열의 처음 인덱스로 순환시킨다.

원형 큐의 상태를 판단하기 위해 일반적으로 두 가지 방법을 사용한다. 하나는 배열에 하나의 공간을 항상 비워두고, rear의 다음 위치가 front와 같으면 큐가 가득 찬 것으로 판단하는 방법이다. 다른 하나는 현재 데이터의 개수를 저장하는 별도의 변수를 사용하여 관리하는 방법이다. 원형 큐는 배열을 기반으로 하면서도 공간을 효율적으로 재사용할 수 있어, 운영체제의 프로세스 스케줄링이나 네트워크 패킷 버퍼링과 같이 고정된 크기의 버퍼가 지속적으로 필요한 시스템 소프트웨어 구현에 널리 활용된다.

우선순위 큐는 일반적인 큐 (자료구조)와 달리, 데이터를 저장된 순서가 아닌 각 요소에 부여된 우선순위에 따라 출력 순서가 결정되는 자료구조이다. 즉, 선입선출(FIFO) 방식을 따르지 않으며, 항상 가장 높은(또는 가장 낮은) 우선순위를 가진 요소가 가장 먼저 제거된다. 이는 마치 병원의 응급실에서 중증도를 기준으로 환자를 진료하는 것과 유사한 방식으로 동작한다.

우선순위 큐는 주로 힙 (자료구조)이라는 트리 기반의 자료구조를 사용하여 효율적으로 구현된다. 이진 힙을 사용할 경우, 요소의 삽입과 최우선순위 요소의 삭제 연산 모두 O(log n)의 시간 복잡도로 수행할 수 있어 매우 효율적이다. 배열이나 연결 리스트로도 구현 가능하지만, 이러한 기본적인 구조를 사용하면 삽입이나 삭제 시 요소들을 재정렬해야 하므로 일반적으로 더 낮은 효율을 보인다.

이 자료구조는 다양한 알고리즘과 시스템에서 폭넓게 응용된다. 대표적으로 다익스트라 알고리즘이나 허프만 코딩과 같은 알고리즘에서 핵심 구성 요소로 사용되며, 운영체제의 작업 스케줄링이나 네트워크 패킷 관리, 이벤트 구동 시뮬레이션 등에서 우선순위가 필요한 작업을 처리할 때 활용된다.

덱은 큐 (자료구조)의 특수한 형태로, 큐와 스택의 성질을 모두 가진 자료구조이다. 덱은 'Double-Ended Queue'의 약자로, 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능한 구조이다. 이로 인해 선입선출 방식과 후입선출 방식 모두를 선택적으로 사용할 수 있어 매우 유연한 데이터 관리를 가능하게 한다.

덱의 주요 연산으로는 양쪽 끝에 원소를 추가하는 addFront, addRear와 양쪽 끝에서 원소를 제거하는 deleteFront, deleteRear가 있다. 또한 양쪽 끝의 원소를 확인하는 연산도 제공된다. 이러한 특성 덕분에 덱은 데이터의 흐름이 양방향으로 이루어져야 하는 다양한 알고리즘과 시스템에서 활용된다.

덱은 주로 스레드 간 메시지 전달, 스케줄링 알고리즘, 캐시 구현, 그리고 특정 검색 알고리즘에서 사용된다. 예를 들어, 슬라이딩 윈도우 최대값을 찾는 문제나 팰린드롬 검사와 같은 알고리즘에서 덱을 효율적으로 사용할 수 있다.

구현 방법에 따라 덱은 배열을 이용한 원형 덱과 연결 리스트를 이용한 덱으로 나눌 수 있다. 배열 구현은 인덱스 접근이 빠르지만 크기가 고정될 수 있는 반면, 연결 리스트 구현은 동적 크기 조정이 용이하지만 노드 간 포인터로 인한 오버헤드가 존재한다.